package com.datastructure.test.mergebinarytree;

public class MergeBinaryTree {

    public static void main(String[] args) {
        TreeNode tree1 = new TreeNode(1);
        tree1.left=new TreeNode(3);
        tree1.right=new TreeNode(2);
        tree1.left.left=new TreeNode(5);
        TreeNode tree2 = new TreeNode(2);
        tree2.left=new TreeNode(1);
        tree2.left.right=new TreeNode(4);
        tree2.right=new TreeNode(3);
        tree2.right.right=new TreeNode(7);
        MergeBinaryTree mergeBinaryTree = new MergeBinaryTree();
        TreeNode treeNode = mergeBinaryTree.mergeTrees(tree1, tree2);
        System.out.println(treeNode);
    }

    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        // write code here
        if(t1!=null&&t2!=null){
            t1.val+=t2.val;
        }
        if(t1==null){
            return t2;
        }
        if(t2==null){
            return t1;
        }
        goingMergeTrees(t1,t1.left,t2.left,true);
        goingMergeTrees(t1,t1.right,t2.right,false);
        return t1;
    }

    private void goingMergeTrees(TreeNode t1Parent, TreeNode t1, TreeNode t2,boolean flag) {
        if(t1==null&&t2==null){
            return;
        }
        if(t1!=null&&t2!=null){
            t1.val+=t2.val;
        }
        if(t1==null){
            if(flag){
                t1Parent.left=t2;
            }else {
                t1Parent.right=t2;
            }
        }
        if(t1!=null&&t2!=null){
            goingMergeTrees(t1,t1.left,t2.left,true);
            goingMergeTrees(t1,t1.right,t2.right,false);
        }
    }
}

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
